#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <unistd.h>

typedef struct STACK Stack;
typedef struct BINTREE BT;
typedef BT* ElementType;
typedef int NodeType;
struct STACK{
	ElementType Elm;
	Stack *Next;
};
struct BINTREE{
	NodeType Elm;
	_Bool Tag;
	BT *Left;
	BT *Right;
};
Stack *StackInit();
_Bool StackEmpty(Stack*);
void  Push(Stack*,ElementType);
ElementType Pop(Stack*);


Stack *StackInit(){
	Stack *s=malloc(sizeof(Stack));
	s->Next=NULL;
	return s;
}

_Bool StackEmpty(Stack *s){
	if( s->Next )
		return false;
	return true;
}
void Push(Stack *s,ElementType x){
	Stack *new=malloc(sizeof(Stack));
	new->Elm=x;
	new->Next=s->Next;
	s->Next=new;
	return;
}
ElementType Pop(Stack *s){
	ElementType x=s->Next->Elm;
	Stack *tmp=s->Next;
	s->Next=tmp->Next;
	free(tmp);
	return x;
}
void Mid_Order(BT *root){
	Stack *s=StackInit();
	BT *current=root;
	while( current || !StackEmpty(s) ){
		while( current ){
			Push(s,current);
			current=current->Left;
		}
		// print function
		current=Pop(s);
		printf("%4d",current->Elm);
		//if( current->Right )
		current=current->Right;
	}
	return;
}
void Pre_Order(BT *root){
	Stack *s=StackInit();
	BT *current=root;
	while( current || !StackEmpty(s) ){
		while( current ){
			printf("%4d",current->Elm);
			Push(s,current);
			current=current->Left;
		}
		// print function
		current=Pop(s);
		//printf("%4d",current->Elm);
		//if( current->Right )
		current=current->Right;
	}
	return;
}
void Post_Order(BT *root){
	Stack *s=StackInit();
	BT *current=root;
	while( current || !StackEmpty(s) ){
		while( current ){
			current->Tag=false;
			Push(s,current);
			current=current->Left;
		}
		current=Pop(s);
//printf("Pop %d Tag:%s\n",current->Elm,current->Tag?"T":"F");
		if( current->Tag ){
			printf("ELM:%4d\n",current->Elm);
			current=Pop(s);
		}
		else{
			current->Tag=true;
			Push(s,current);
			current=current->Right;
		}
	}
	return;
}
void Post_Order_2(BT *root){
	BT *current=root;
	Stack *s=StackInit();
	Stack *ret=StackInit();
	while( current || !StackEmpty(s) ){
		while( current ){
			//printf("%4d",current->Elm);
			Push(ret,current);
			Push(s,current);
			current=current->Right;
		}
		current=Pop(s);
		current=current->Left;
	}

	while( !StackEmpty(ret) )printf("%5d",Pop(ret)->Elm);
	return;
}
int max(int a,int b){
	return a>=b?a:b;
}
int In_Order(BT *root){
	if( !root )
		return 0;
	//if( !root->Left && !root->Right )
	printf("%5d",root->Elm);
	int l,r;
	l=In_Order(root->Left);
	r=In_Order(root->Right);
	return max(l,r)+1;
}
BT* NewBT(NodeType x){
	BT *b=malloc(sizeof(BT));
	b->Elm=x;
	b->Left=b->Right=NULL;
	return b;
}
void AddLeft(BT *root,NodeType x){
	BT *b=malloc(sizeof(BT));
	b->Elm=x;
	b->Left=b->Right=NULL;
	root->Left=b;
	return;
}
void AddRight(BT *root,NodeType x){
	BT *b=malloc(sizeof(BT));
	b->Elm=x;
	b->Left=b->Right=NULL;
	root->Right=b;
	return;
}
int main(){
	BT *b=NewBT(15);
	AddLeft(b,11);
	AddRight(b,20);
	AddLeft(b->Left,30);
	AddRight(b->Left,2);
	AddRight(b->Right,1);
	AddLeft(b->Right->Right,9);
	//Mid_Order(b);
	//Pre_Order(b);
	//Post_Order_2(b);
	int a=In_Order(b);
	printf("\nHigh:%4d\n",a);
	return 0;
}
